/*
 * Copyright 2012 Alain Pannetrat (L1L1@gmx.com)
 * 
 * This file is part of cookie-miner.
 * 
 * cookie-miner is free software: you can redistribute it and/or modify 
 * it under the terms of the GNU General Public License as published by 
 * the Free Software Foundation, either version 3 of the License, or 
 * (at your option) any later version.
 * 
 * cookie-miner is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License 
 * along with cookie-miner. If not, see http://www.gnu.org/licenses/.
 *
 * @version: $Id$
 *
 */
#ifndef _QUADTREE_H_
#define _QUADTREE_H_

#include "graphs.h"
#include "vectors.h"

class QNode {
	public:
		// these custom new/delete function allow fast memory recycling.
		static void *operator new(size_t sz);
		static void operator delete(void *nd);

		static QNode* create(float left, float top, float right, float bottom) {
			return new QNode(left,top,right,bottom); }

		Vertex* vertex() const { return _vertex; }

		const Vector& position() const { return _position; } 

		float weight() const { return _weight; }

		float surface() const { return (_right-_left)*(_bottom-_top); }

		void area(float &left, float &top, float &right, float &botton);
		// area() is an accessor for rectangular area of quad

		void traverse(bool (*trav_func)(QNode*,void *), void *data);

		void add(Vertex* v);

		//void dump(const char *title, unsigned depth=0);

		~QNode();
	private:
		QNode(float left, float top, float right, float bottom):
			_top(top),
			_bottom(bottom),
			_right(right),
			_left(left)
			// other members are set to NULL by default 
			// see new() and delete()
			{ }

		void force_add(Vertex* v);
		QNode *_next_free;		// used for free list, see new()
		Vector _position;		// centered average position
		float _weight;			// number of vertices in the quad

		float _top;
		float _bottom;
		float _right;
		float _left;
		
		QNode *_tl;			// top-left
		QNode *_tr;			// top-right
		QNode *_bl;			// bottom-left
		QNode *_br;			// bottom-right

		Vertex* _vertex;		// vertex if leaf node or NULL
};

#endif

